#include "QuikSort.h"

void QuikSort::sort(vector<int>& arr)
{
	sort(arr, 0, arr.size() - 1);
}

void QuikSort::sort(vector<int>& arr, int left, int right)
{
	if (left < right)
	{
		swap(arr[right], arr[random(left, right)]);

		vector<int> lAndR = partition(arr, left, right);
		sort(arr, left, lAndR[0] - 1);
		sort(arr, lAndR[1] + 1, right);
	}
}

vector<int> QuikSort::partition(vector<int>& arr, int left, int right)
{
	int edgeL = left - 1;
	int edgeR = right;

	while (left < edgeR)
	{
		if (arr[left] < arr[right])
		{
			swap(arr[++edgeL], arr[left++]);
		}
		else if (arr[left] > arr[right])
		{
			swap(arr[--edgeR], arr[left]);
		}
		else
		{
			left++;
		}
	}

	swap(arr[edgeR], arr[right]);

	vector<int> v = { edgeL + 1,edgeR };

	return v;
}

